\subsection{Ejercicio 3}

El presente filtro "`Bandas"' toma una imagen fuente y genera bandas en varios tonos de gris. Para generar la nueva imagen, se suman las tres componentes de cada pixel (Rojo, Verde, y Azul), y dependiendo del resultado de esta sumatoria, se escribir\'a un valor de p\'ixel determinado en la imagen destino:


\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.60]{imagenes/formulaBandas1.png}
\caption{Formula del filtro Bandas.}
\end{center}
\label{fig:bandas01}
\end{figure}


\subsubsection{Implementaci\'on en C}
La implementaci\'on en C fue relativamente sencilla, limitando el c\'odigo a sumar los valores R-G-B del p\'ixel actual (ignorando el valor de A - Alpha o transparencia -) y, por medio de IFs, saber en que rango de valores se encuentra la sumatoria actual.\\
Lo \'unico a resaltar es que los valores a escribir en la imagen destino, se "`inviertieron"' (respecto del enunciado), debido a que en cada p\'ixel, primero se encuentra el color Azul, luego el Verde, luego el Rojo y, al final el valor de Alpha (que no fue tomado en cuenta, excepto para realizar desplazamientos cada 4 bytes).

El pseudoc\'odigo es el siguiente: 

\begin{codesnippet}
\begin{verbatim}
    sumaActual = 0
    Para i = 0 hasta Alto de la imagen fuente; Paso: i++
        Para j = 0 hasta Ancho de la imagen fuente; Paso: j ++

            sumaActual = Suma de Componentes del pixel actual (i,j*4)
            Si (sumaActual < 96)
                Escribir en el p\'ixel (i,j*4) de la imagen de destino el valor del RANGO 1
            Sino Si (sumaActual < 288)
                    Escribir en el p\'ixel (i,j*4) de la imagen de destino el valor del RANGO 2
                Sino Si (sumaActual < 480)
                        Escribir en el p\'ixel (i,j*4) de la imagen de destino el valor
                        del RANGO 3
                    Sino Si (sumaActual < 672)
                            Escribir en el p\'ixel (i,j*4) de la imagen de destino el valor
                            del RANGO 4
                        Sino
                            Escribir en el p\'ixel (i,j*4) de la imagen de destino el valor
                            del RANGO 5
                    Fin Si
                Fin Si
            Fin Si

        Fin Para
    Fin Para
\end{verbatim}
\end{codesnippet}

\newpage

\subsubsection{Implementaci\'on en ASM}
La implementaci\'on del filtro Bandas en ensamblador posee varias diferencias respecto de la realizada en C. Una de ellas es que en esta implementaci\'on se procesan de a 4 p\'ixeles por iteraci\'on. La raz\'on es sencilla: como cada p\'ixel ocupa 4 bytes (R-G-B-A), 4 p\'ixeles (es decir, 16 bytes) son la mayor cantidad de bytes que se pueden manejar en paralelo.\\

Otra diferencia sustancial, es la detecci\'on de l\'imites y tratamiento de los bordes de la imagen. Para este  filtro, se sigui\'o el siguiente esquema.\\
El hecho de trabajar con 4 p\'ixeles simult\'aneamente da lugar a un caso borde que vale la pena mencionar: cuando se llega al final de una fila y quedan 3 o menos p\'ixeles por procesar. La siguiente figura ilustra la situaci\'on:


\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.90]{imagenes/bordes.png}
\caption{Detecci\'on de bordes en los filtros.}
\end{center}
\label{fig:bandas02}
\end{figure}


El c\'odigo del programa detecta el caso y lo resuelve provocando un retroceso en los contadores de manera tal que los pr\'oximos 4 p\'ixeles a procesar sean precisamente los \'ultimos cuatro de la fila. Como consecuencia de este ajuste, pueden haber hasta 4 p\'ixeles que se procesan por segunda vez, pero sin mayor impacto sobre la performance global de la implementaci\'on.\\

El procesamiento de los 4 p\'ixeles (se obtienen utilizando la instrucci\'on \textit{MOVDQU}), por una cuesti\'on de precisi\'on, se realiza en dos pasos distintos (se procesan dos en paralelo, y luego los otros dos, y finalmente se empaqueta el resultado, para obtener los 4 p\'ixeles resultantes). Es por esta raz\'on que los 4 p\'ixeles obtenidos de la imagen de origen son copiados en dos registros XMM diferentes, para luego ser desempaquetados convenientemente (utilizando las instrucciones \textit{PUNPCKLBW} para procesar los primeros 2 p\'ixeles, y \textit{PUNPCKHBW} para procesar los \'ultimos 2 p\'ixeles). Estos desempaquetamientos son realizados para no perder precisi\'on a la hora de realizar la suma de las 3 componentes R-G-B de cada p\'ixel (recordemos que la componente A no se la toma en cuenta a la hora de realizar los c\'alculos y se la deja en 0 en la imagen de destino).\\

Este es justamente el primer paso que se realiza luego del desempaquetamiento, de la siguiente manera:
Se copian los valores R-G-B-A de cada uno de los 2 p\'ixeles que se procesar\'an en paralelo en tres registros distintos. Esto es para que, realizando un shift (con  la instrucción \textit{PSRLDQ}) de dos bytes en uno, y de cuatro bytes en otro, se puedan ``alinear'' los valores R-G-B-A de los p\'ixeles, y as\'i realizar la suma (utilizando \textit{PADDW}), tal como se puede apreciar a continuaci\'on:

\begin{verbatim}
	XMM0 = |B1 |G1 |R1 |A1 |B2 |G2 |R2 |...|
+
	XMM3 = |G1 |R1 |A1 |B2 |G2 |R2 |.......|
+
	XMM4 = |R1 |A1 |B2 |G2 |R2 |...........|
	------------------------------------
	XMM0 = |R1+G1+B1|...|...|...|R2+G2+B2|...|
\end{verbatim}

Ahora bien, por una cuesti\'on de conveniencia, se utiliz\'o una m\'ascara para poner los valores que no fueran la suma en 0, y se procedi\'o a acomodar la suma de la siguiente manera:

\begin{verbatim}
	XMM0 = |sumaP1|   0  |   0  |   0  |sumaP2|   0  |   0  |   0  |
+
	XMM3 = |   0  |sumaP1|   0  |   0  |   0  |sumaP2|   0  |   0  |
+
	XMM4 = |   0  |   0  |sumaP1|   0  |   0  |   0  |sumaP2|   0  |
	------------------------------------
	XMM0 = |sumaP1|sumaP1|sumaP1|   0  |sumaP2|sumaP2|sumaP2|   0  |
\end{verbatim}

La raz\'on este acomodamiento es sencilla: al momento de verificar a que rango pertenece cada p\'ixel, se sabe que las 3 componentes pertenecer\'an al mismo rango. Utilizando m\'ascaras (y la instrucci\'on \textit{PCMPGTW}) se sabe cuales de estas sumas son menores a 96, cuales menores a 288, cuales menores a 480, cuales menores a 672 y cuales mayores. A su vez, sabiendo cuales no son menores a 96 (es decir, mayores o iguales) y cuales son menores a 288, se puede determinar cuales p\'ixeles est\'an, por ejemplo, en el segundo rango. De la misma manera sucede con los dem\'as rangos.\\

Finalmente, al empaquetar los datos (por medio de la instruacción \textit{PACKUSWB}) se obtienen, en dos registros diferentes, los valores de los 4 p\'ixeles que se escribir\'an en la imagen de destino. Haciendo un shift (usando \textit{PSLLDQ}) del registro XMM que tiene los \'ultimos 2 p\'ixeles, y sumando eso al registro que tiene los primeros 2, se obtienen los 4 p\'ixeles en un \'unico registro XMM, que se pasar\'a de manera directa a la imagen destino.\\

\newpage

El pseudoc\'odigo de la implementaci\'on en ensamblador es el siguiente:

\begin{codesnippet}
\begin{verbatim}

    Para i = 0 hasta Alto de la imagen fuente
        Para j = 0 hasta Ancho de la imagen fuente; Paso: j += 4

            -> Cargar en XMM0 los próximos 4 píxeles de la imagen fuente a partir 
            del píxel [i][j].
            -> Copiar esos píxeles en el registro XMM7

            -> Desempaquetar y cargar las 4 componentes de los primeros 2 píxeles de XMM0.
            -> Copiar esas componentes en otros 2 registros (XMM3 y XMM4).
            -> Hacer un "Shift Right" de los 2 registros, de manera que las componentes 
            de los píxeles queden alineados.
            -> Sumar los registros XMM3, XMM4 y XMM0 para obtener las sumas de los 3 componentes 
            de los primeros dos píxeles.
            -> Duplicar esas sumas en XMM0, de manera que se repitan 3 veces contiguas 
            para cada píxel (como fue explicado anteriormente)

            -> Copiar la máscara correspondiente al RANGO 1 en XMM9 (96)
            -> Comparar esa máscara con el registro XMM0 (con PCMPGTW)
            -> Hacerle PXOR al registro XMM0 (porque siempre serán cero todos los valores del
            primer rango)
            -> Invertir los bits del resultado de la comparación

            -> Copiar la máscara correspondiente al RANGO 2 en XMM8 (288)
            -> Comparar esa máscara con el registro XMM0 (con PCMPGTW)
            -> Hacerle AND al resultado de esta comparación con la guardada en XMM9 
            (del resultado anterior)
            -> Hacerle AND a este resultado con el valor de los píxeles en el segundo rango
            -> Invertir los bits del resultado de la comparación de XMM0 con XMM8

            -> Hacer lo mismo con el RANGO 3 y RANGO 4
            -> Para el RANGO 5, sólo invertir los bits de la última comparación
            -> Y hacerle AND a este resultado con el valor de los píxeles en el quinto rango

            -> Procesar el segundo grupo de 2 píxeles de la misma manera que para 
            los primeros dos.

            -> Empaquetar los resultados de los píxeles en XMM0 y XMM7 (usando la instrucción 
            PACKUSWB, para saturarlo y filtrar los valores negativos que pudieran haber).

            -> Usando Shifts, guardar los valores de los 4 píxeles resultantes en XMM0

            -> Guardar píxeles de XMM0 en la imagen de destino a partir del píxel [i][j].

        Fin Para
    Fin para

\end{verbatim}
\end{codesnippet}

\newpage

\subsubsection{Experimentos y An\'alisis de resultado}

Para los experimentos de este filtro, se ha utilizado un procesador \textit{Intel Dual Core E5200 2,5 Ghz}, y se han realizado 100 ejecuciones por prueba, tomando el promedio de la cantidad de ticks de reloj, para obtener un valor m\'as preciso en las mediciones.\\
Se han hecho 3 tipos de prueba: con imagenes cuadradas de tamaño creciente, con imagenes de ancho creciente solamente, y con imagenes de alto creciente. La raz\'on para esto es para saber como var\'ia la performance del filtro ante imagenes cada vez m\'as grandes, teniendo que procesar cada vez una mayor cantidad de p\'ixeles (el caso de imagenes cuadradas); ante imagenes cada vez m\'as anchas, tieniendo que procesar cada vez filas m\'as grandes (pero con menos ciclos, dado que tiene pocas filas); y ante imagenes cada vez m\'as altas, teniendo que procesar cada vez una mayor cantidad de filas (pero relativamente cortas, teniendo que ciclar muchas veces sobre filas).\\
\\

\textbf{Experimento 1 - "Saltos condicionales"}

Para este experimento se ha comparado la ejecuci\'on del filtro Bandas en C, con otro (tambi\'en en C) pero que no tuviera las l\'ineas de c\'odigo referidas a detectar a que banda pertenece cada p\'ixel (aunque la imagen resultante no fuera correcta), utilizando en ambos casos el flag de compilaci\'on \textit{-O1}.\\
Tal como se nombr\'o anteriormente, se realizaron 3 grupos de pruebas, que permitir\'an evaluar distintos aspectos del filtro, y comprobar si en alguno de esos escenarios los saltos condicionales tienen un mayor o menor impacto.\\
A continuaci\'on se detallan los 3 escenarios:\\


\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.70]{imagenes/grafico3-1.png}
\caption{Pruebas con el filtro Bandas, para imagenes cuadradas de tamaño creciente.}
\end{center}
\label{fig:bandas02}
\end{figure}

\newpage

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.70]{imagenes/grafico3-2.png}
\caption{Pruebas con el filtro Bandas, para imagenes de alto creciente.}
\end{center}
\label{fig:bandas03}
\end{figure}


\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.70]{imagenes/grafico3-3.png}
\caption{Pruebas con el filtro Bandas, para imagenes de ancho creciente.}
\end{center}
\label{fig:bandas04}
\end{figure}

Tal como se puede apreciar en los gr\'aficos mostrados, se muestra una diferencia de performance superior al 40\%, entre el caso del c\'odigo que posee salto condicionales respecto del que no, para imagenes cuadradas. Estas tienen la particularidad de ser "`uniformes"' respecto del procesamiento de p\'ixeles, teniendo por unico objetivo el verificar el comportamiento del filtro frente a una cantidad creciente de p\'ixeles que se deben procesar. Tanto en la imagenes de ancho como en las de alto variable se aprecia una diferencia de performance cada vez mayor (de 3 a 4 veces mayor uno respecto del otro).\\

\newpage

\textbf{Experimento 2 - "secuencial vs vectorial"}

Para este experimento se compararon las ejecuciones del filtro Bandas en C con los flags de compilaci\'on \textit{-O0, -O1, -O2 y -O3}, con otras sin ellos, con la versi\'on en Assembler.\\
Dado que en los experimentos iniciales se mostraba una clara mejor perfomance en la versi\'on en C con los flags respecto de la versi\'on en Assembler (no se considera el caso en C sin los flags de compilaci\'on, dado que se esperaba que sus tiempos de ejecuci\'on fueran mayores), se procedi\'o a buscar el origen de tal "`Anomal\'ia"'. Y se descubri\'o que la diferencia entre la performance entre ambas versiones proven\'ia de la ejecuci\'on de c\'odigo en Assembler que, dentro del ciclo principal, obtuviera valores de memoria (en vez de guardarlos en registros y utilizarlos luego). Optimizando el uso de registros de 128 bits, se logr\'o hacer esto, mejorando notablemente los tiempos de ejecuci\'on, tal como se muestra a continuaci\'on:\\


\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.70]{imagenes/grafico3-4.png}
\caption{Pruebas con el filtro Bandas, para imagenes cuadradas de tamaño creciente.}
\end{center}
\label{fig:bandas05}
\end{figure}


\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.70]{imagenes/grafico3-5.png}
\caption{Pruebas con el filtro Bandas, para imagenes de alto creciente.}
\end{center}
\label{fig:bandas06}
\end{figure}


\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.70]{imagenes/grafico3-6.png}
\caption{Pruebas con el filtro Bandas, para imagenes de ancho creciente.}
\end{center}
\label{fig:bandas07}
\end{figure}


Tal como se ha anticipado, estos experimentos muestran como, por medio de los flags de optimizaci\'on, se logra una perfomance muy similar (y por momentos, super\'andola) a la del c\'odigo en Assembler (luego de unas optimizaciones realizadas a este \'ultimo), tal como se esperaba. La diferencia entre ambos y el c\'odigo C sin flag alguno ronda casi el 280\%. La explicaci\'on para esta diferencia se puede encontrar en el procesamiento en paralelo de a 4 p\'ixeles, contra 1 de la versi\'on en C sin flags.\\
El resultado sorpresivo ha sido el hecho de que, por momentos, la implementaci\'on en C con flags de optimizaci\'on supera en performance a la de Assembler. Si bien el c\'odigo en Assembler ha sido optimizado para lograr este resultado (tal como fue explicado en un principio), existen algunos factores que pueden hacer que no se encuentre lo m\'as optimizado posible. Uno de estos podr\'ia ser el retroceso que se realiza para no superar los bordes, aunque en este caso no influye, dado que todas las imagenes testeadas han sido m\'ultiplos de 4. Sin embargo, sin necesidad de reprocesar p\'ixeles, los c\'alculos que se hacen para el tratamiento de bordes pueden agregar un overhead respecto de la implementaci\'on en C.